import common.ListNode;

/**
 * Created with IntelliJ IDEA.
 * Description: 第一题：反转链表
 */
public class Test1 {
    public static void main(String[] args) {

    }

    // 方法一：创建一个新的头节点
    // 遍历链表
    // 将每个节点都插入到
    public ListNode ReverseList(ListNode head) {
        // 设置新的头节点
        ListNode newHead = null;
        // 使用 cur 进行链表的遍历
        ListNode cur = head;
        while(cur != null) {
            // 对链表进行遍历，将之后的每一个节点的 next 值进行保存
            ListNode tmp = cur.next;
            // 此时该节点已经独立，将该节点插入到新链表的最前面
            // 由于 newHead 初始值是 null，因此循环第一次就把原来的头节点的 next 值置为了 null
            // 不存在出现环的情况
            cur.next = newHead;
            // 新链表的头节点改成新的
            newHead = cur;
            // 将 cur 在旧链表上往后移一个节点
            cur = tmp;
        }
        // 返回 newHead.next
        return newHead;
    }
}
